import java.util.List;

public class Demo3 {

    public static void main(String[] args) {

    }







    int[] tmp;
    public int reversePairs(int[] nums) {

        int n = nums.length;
        tmp = new int[n];
        return mergeSort1(nums,0,n-1);
    }

    private int mergeSort1(int[] nums, int left, int right) {
        if (left>=right){
            return 0;
        }

        int ret = 0;
        //1.选择中间点
        int mid = (left+right)/2;
        //[left,mid]  [mid+1,right]

        //2.找左边的个数  + 排序 + 有半部分  + 排序
        ret+=mergeSort1(nums,left,mid);
        ret+=mergeSort1(nums,mid+1,right);

        //3.处理一左一有的个数
        int cur1 = left,cur2=mid+1,i=0;
        while (cur1<=mid && cur2<=right){
            if (nums[cur1]<=nums[cur2]){
                tmp[i++] = nums[cur1++];
            }else {
                ret+=mid-cur1+1;
                tmp[i++] = nums[cur2++];
            }
        }

        //4.处理排序
        while (cur1<=mid){
            tmp[i++] = nums[cur1++];
        }
        while (cur2<=right){
            tmp[i++] = nums[cur2++];
        }
        for(int j = left;j<=right;j++){
            nums[j] = tmp[j-left];
        }
        return ret;


    }


    public int[] sortArray(int[] nums) {
        mergeSort(nums,0,nums.length-1);
        return nums;
    }

    private void mergeSort(int[] nums, int left, int right) {
        if (left>=right){
            return;
        }

        //根据中间点划分区间
        int mid = (left+right)/2;

        //2.先把左右区间排序
        mergeSort(nums,left,mid);
        mergeSort(nums,mid+1,right);

        //3.合并两个有序数组
        int[] tmp = new int[right-left+1];
        int cur1 = left;
        int cur2 = mid+1;
        int i = 0;
        while (cur1<=mid && cur2<=right){
            tmp[i++] = nums[cur1] <= nums[cur2]?nums[cur1++]:nums[cur2++];
        }
        //处理没有遍历完的数组
        while (cur1<=mid){
            tmp[i++] = nums[cur1++];
        }
        while (cur2<=right){
            tmp[i++] = nums[cur2++];
        }

        //4.还原
        for(int j =left;j<=right;j++){
            nums[j] = tmp[j-left];
        }

    }



}
